package problem;

import java.util.Iterator;
import java.util.LinkedList;

import instance.InstanceResultado;
import instance.InstanceTP3;

public class Tabu {

	private LinkedList<Integer> circuito1;
	private LinkedList<Integer> circuito2;
	private int[][] pesos;
	private int cant_nodos;
	private int nodo_origen;
	private InstanceTP3 pes;
	private int res;
	private LinkedList<tabu_t> lista_tabu;
	InstanceResultado inst;
	private int size_lista;
	private boolean minimo_local = false;
	public static int min_loc;
	
	private int res_iter;
	private int res_sol;
	
	private LinkedList<String> res_graf;
	public LinkedList<Integer> progreso_soluciones;
	
	public static int contador_Tabu;
	
	public Tabu (InstanceResultado instt, InstanceTP3 inst_pesos, int size_lista, int cant_iteraciones){
		/*IMPORTANTE: dado que el rendimiento (tiempo) no es importante y para ahorrar código y tiempo de los 
		 * programadores, nos guardamos el progreso de las soluciones hasta llegar al mínimo local. */
		progreso_soluciones = new LinkedList<Integer>();
		
		/* En inst recibo el resultado de la constructiva u otra soluci�n cualquiera */
		
		lista_tabu = new LinkedList<tabu_t>();
		this.size_lista = size_lista;
		
		this.inst = instt;
		this.pesos = inst_pesos.matriz;
		this.pes = inst_pesos;
				/* La cantidad de nodos es la cantidad que esta en los ciclos mas el nodo_origen*/
		this.cant_nodos = inst.getPrimer_ciclo().size() + inst.getSegundo_ciclo().size() + 1;
		this.nodo_origen = inst.getNodo_origen();
		
				/* Agrego el nodo_origen al principio y al final de cada ciclo */
		// tengo que copiarlos
		
//		System.out.println("Lo que recibo como parametro:");
//		System.out.println("	Nodo Origen: " +inst.getNodo_origen());
//		System.out.println("	Primer Circuito: " +inst.getPrimer_ciclo());
//		System.out.println("	Segundo Circuito: " +inst.getSegundo_ciclo());
		
		
		this.inst.getPrimer_ciclo().addFirst(this.nodo_origen);
		this.inst.getPrimer_ciclo().addLast(this.nodo_origen);
		this.circuito1 = new LinkedList<Integer>(inst.getPrimer_ciclo());
		
		this.inst.getSegundo_ciclo().addFirst(this.nodo_origen);
		this.circuito2 = new LinkedList<Integer>(inst.getSegundo_ciclo());
		this.inst.getSegundo_ciclo().addLast(this.nodo_origen);
				
		
		
		int peso_inicial = calcularPeso(inst);
//		System.out.println("--- " +calcularPeso(inst) +" ---\n");
		
		boolean criterio_de_parada = false;
		int iteraciones = 0;
		
		
		res_iter = 0;
		res_sol = 0;
		
		res_graf = new LinkedList<String>();
		
		MejorParcial mp = new MejorParcial();
		// mientras no pase algun criterio de parada a definir
		while(!criterio_de_parada && iteraciones < cant_iteraciones){
			iteraciones++;
				/* Elijo mejor solucion */
			// en mp voy a ir guardando el mejor movimiento posible
			
			//System.out.println(lista_tabu);
//			//System.out.println("circ1.size: " +this.circuito1.size());
//			//System.out.println("circ2.size: " + this.circuito2.size());
//			mp = dameElMejorVecino();
			
			/*
			 * Si el nuevo movimiento es peor que el que tenia: -> tabu
			 * Sino y si el nuevo movimiento es mejor que el mejor que tenia: -> actualizar mejor
			 * Sino no hago nada 
			 */
			
			MejorParcial mejorVecino = dameElMejorVecino();
			progreso_soluciones.add(mejorVecino.getPesoTotal());
			
			modificarCircuitos(mejorVecino);
			//System.out.println("MEJOR_VECINO: " +mejorVecino.getPesoTotal());
			
			if(mp.getPesoTotal() != 0 && mejorVecino.getPesoTotal() > mp.getPesoTotal()){
				if(!minimo_local) {
					minimo_local = true;
					//System.out.println("��Alcanc� el m�nimo!!");
					min_loc = mp.getPesoTotal();
				}
				agregarTabu(mejorVecino);
				mp = mejorVecino;
			}else if(mejorVecino.getPesoTotal()!=0 && mejorVecino.getPesoTotal() < calcularPeso(inst)){
				if(minimo_local){
					//System.out.println("��Mejor� el m�nimo local!!");
				}
				actualizarInstancia();
	//			agregarTabu(mp);				
			}else{
				if(!minimo_local) {
					minimo_local = true;
					//System.out.println("��Alcanc� el m�nimo!!");
					min_loc = mp.getPesoTotal();
				}
				agregarTabu(mejorVecino);
			}
			
			
			res_graf.add(iteraciones +" " +calcularPeso(inst));
			
			if (res_sol == 0 || calcularPeso(inst) < res_sol){
				res_sol = calcularPeso(inst);
				res_iter = iteraciones;
			}
			
			
			/* en MP tengo la mejor soluci�n vecina */
			
//			modificarCircuitos(mp);
//			//System.out.println("MMPP: " +mp.getPesoTotal());
//			
//			if(mp.getPesoTotal()!=0 && mp.getPesoTotal() < calcularPeso(inst)){
//				if(minimo_local){
//					//System.out.println("��Mejor� el m�nimo local!!");
//				}
//				actualizarInstancia();
////				agregarTabu(mp);
//			}else{
//				if(!minimo_local) {
//					minimo_local = true;
//					//System.out.println("��Alcanc� el m�nimo!!");
//				}
//				agregarTabu(mp);
//			}
			
			
		}
		
//		//System.out.println(inst.getPrimer_ciclo());
//		//System.out.println(inst.getSegundo_ciclo());
		this.res = calcularPeso(inst);
//		//System.out.println("Tama�o ListaTabu: Deberia ser " +size_lista +" pero es " +this.lista_tabu.size());
//		System.out.println("Lo que devuelvo: " +this.res);
		if(peso_inicial < this.res) System.out.println("AAAAAAAAAAAAAAAAA EMPEOREEEEEEEEEEEEEEEEEEEEEEEEEEEEEE");
	}

	private MejorParcial dameElMejorVecino() {
		
		MejorParcial mp = new MejorParcial();
		
		int tmp, w1, w2, valor, pos1, pos2;
		Iterator<Integer> it, it2;
		
		/* Primero saco los nodos del primer ciclo */		
		if(this.circuito1.size() != 4){
			for(int i=1; i<this.circuito1.size()-1; i++){
				valor = this.circuito1.get(i);
					/* Saco el elemento i */
				this.circuito1.remove(i);
					
					/* Itero por el primer ciclo viendo el costo de agregar en cada par de nodos consecutivo */
				it = this.circuito1.iterator();
				pos1 = 0;
				it2 = this.circuito1.iterator();
				it2.next();
				pos2 = 1;
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
						/* Si este movimiento es valido y me mejora lo que tenia, actualizo. */
//					//System.out.println(esMovimientoValido(valor, w1, w2));
					if(esMovimientoValido(valor, w1, w2, 1) && ((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0)){
							
						//System.out.println("1- esValido: " +esMovimientoValido(valor,w1,w2, 1) +" mp: " +mp.getPesoTotal() + " tmp: " + tmp);
						//System.out.println("Muevo " +valor +" entre " +w1 +" y " +w2);
						////System.out.println("circ1.size: " +this.circuito1.size());
						////System.out.println("circ2.size: " + this.circuito2.size());
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2);
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(1);		mp.setCircuitoSacar(1);
					}
	
					pos1++;
					pos2++;
				}
				
					/* Ahora itero por el segundo ciclo */
				it = this.circuito2.iterator();
				pos1 = 0;
				it2 = this.circuito2.iterator();
				it2.next();
				pos2 = 1;
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
						/* Si este movimiento es valido y me mejora lo que tenia, actualizo. */
					if(esMovimientoValido(valor, w1, w2, 2) && ((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0)){
						
						//System.out.println("2- esValido: " +esMovimientoValido(valor, w1, w2, 2) +" mp: " +mp.getPesoTotal() + " tmp: " + tmp);
						//System.out.println("Muevo " +valor +" entre " +w1 +" y " +w2);
						////System.out.println("circ1.size: " +this.circuito1.size());
						////System.out.println("circ2.size: " + this.circuito2.size());
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2);
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(2);		mp.setCircuitoSacar(1);
					}
	
					pos1++;
					pos2++;
				}
				
				/* Vuelvo a agregar el elemento donde estaba */
				this.circuito1.add(i, valor);
			}
		}
		
			/* En este caso, voy a sacar los elementos del segundo circuito */
		if(this.circuito2.size()!=4){
			for(int i=1; i<this.circuito2.size()-1; i++){
				valor = this.circuito2.get(i);
				this.circuito2.remove(i);
				
					/* Itero por el primer ciclo viendo el costo de agregar en cada par de nodos consecutivo */
				it = this.circuito1.iterator();
				pos1 = 0;
				it2 = this.circuito1.iterator();
				it2.next();
				pos2 = 1;
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
						/* Si este movimiento es valido y me mejora lo que tenia, actualizo. */
//					//System.out.println(esMovimientoValido(valor, w1, w2));
					if(esMovimientoValido(valor, w1, w2, 1) && ((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0)){

						//System.out.println("3- esValido: " +esMovimientoValido(valor, w1, w2, 1) +" mp: " +mp.getPesoTotal() + " tmp: " + tmp);
						//System.out.println("Muevo " +valor +" entre " +w1 +" y " +w2);
						////System.out.println("circ1.size: " +this.circuito1.size());
						////System.out.println("circ2.size: " + this.circuito2.size());
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2);
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(1);		mp.setCircuitoSacar(2);
					}
		
					pos1++;
					pos2++;
				}
				
					/* Ahora itero por el segundo */
				it = this.circuito2.iterator();
				pos1 = 0;
				it2 = this.circuito2.iterator();
				pos2 = 1;
				it2.next();
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
						/* Si este movimiento es valido y me mejora lo que tenia, actualizo. */
					if(esMovimientoValido(valor, w1, w2, 2) && ((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0)){
						
						//System.out.println("4- esValido: " +esMovimientoValido(valor, w1, w2, 2) +" mp: " +mp.getPesoTotal() + " tmp: " + tmp);
						//System.out.println("Muevo " +valor +" entre " +w1 +" y " +w2);
//						//System.out.println("circ1.size: " +this.circuito1.size());
//						//System.out.println("circ2.size: " + this.circuito2.size());
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2); 
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(2);		mp.setCircuitoSacar(2);
					}
					pos1++;
					pos2++;
				}
				this.circuito2.add(i, valor);
			}
		}
		
		return mp;
	}




	private void actualizarInstancia() {
		this.inst.setPrimer_ciclo(new LinkedList<Integer>(this.circuito1));
		this.inst.setSegundo_ciclo(new LinkedList<Integer>(this.circuito2));
	}

	private boolean esMovimientoValido(int valor, int w1, int w2, int circ_a_insertar) {
		
		Iterator<tabu_t> it = this.lista_tabu.iterator();
		while(it.hasNext()){
			tabu_t t = it.next();
			
			if(circ_a_insertar == 1){
				//inserto en el circuito 1. No me interesa de donde saco ya que ese circuito esta correctamente modificado
				if(t.getPrimero() == w1 && t.getSegundo() == w2 && t.getMedio() == valor
						&& t.getCirc1_size() == (this.circuito1.size()+1) 
						&& t.getCirc2_size() == this.circuito2.size()){
					return false;
				}
			}else{
				//inserto en el 2
				if(t.getPrimero() == w1 && t.getSegundo() == w2 && t.getMedio() == valor
						&& t.getCirc1_size() == this.circuito1.size()
						&& t.getCirc2_size() == (this.circuito2.size()+1)){
					return false;
				}
			}
			
			
//			if(saco == 1 && pongo == 1){
//				// saco y pongo de/en el circuito 1. Por ende, no se me modifican los tama�os de los circuitos
//				if(t.getPrimero() == w1 && t.getSegundo() == w2 && t.getMedio() == valor
//						&& t.getCirc1_size() == this.circuito1.size() && t.getCirc2_size() == this.circuito2.size()){
//					return false;
//				}
//			}else if(saco == 1 && pongo == 2){
//				if(t.getPrimero() == w1 && t.getSegundo() == w2 && t.getMedio() == valor
//						&& t.getCirc1_size() == (this.circuito1.size()-1) && t.getCirc2_size() == (this.circuito2.size()+1)){
//					return false;
//				}
//			}else if(saco == 2 && pongo == 2){
//				if(t.getPrimero() == w1 && t.getSegundo() == w2 && t.getMedio() == valor
//						&& t.getCirc1_size() == this.circuito1.size() && t.getCirc2_size() == this.circuito2.size()){
//					return false;
//				}
//			}else{
//				//saco del 2 y pongo en el 1
//				if(t.getPrimero() == w1 && t.getSegundo() == w2 && t.getMedio() == valor
//						&& t.getCirc1_size() == (this.circuito1.size()+1) && t.getCirc2_size() == (this.circuito2.size()-1)){
//					return false;
//				}
//			}
			
//			if(t.getPrimero() == w1 && t.getSegundo() == w2 && t.getMedio() == valor
//					&& t.getCirc1_size() == this.circuito1.size() && t.getCirc2_size() == this.circuito2.size()){
//				return false;
//			}
		}
		return true;
	}

	private void agregarTabu(MejorParcial mp) {
			/* El tabu_t perfecto seria el que guarda ambos circuitos completos.
			 * Como eso es muy poco eficiente en cuanto a la memoria, hay que guardar
			 * la mayor informacion posible sobre el estado de los circuitos. 
			 * Por ahora, guardamos el movimiento y el tamanio de los circuitos.*/
		
		tabu_t tabuuu = new tabu_t(mp.getW1(), mp.getW2(), mp.getI(), this.circuito1.size(), this.circuito2.size());
		if(lista_tabu.size() == this.size_lista && lista_tabu.size() != 0){
			lista_tabu.removeFirst();
		}
		
//		//System.out.println("SizeTabu: " +lista_tabu.size());
		this.lista_tabu.add(tabuuu);
	}

	public int calcularPeso(InstanceResultado inst) {
		int peso = 0;
		int w1, w2;
		
		LinkedList<Integer> c1 = inst.getPrimer_ciclo();
		LinkedList<Integer> c2 = inst.getSegundo_ciclo();
		Iterator<Integer> it, it2;
		
		it = c1.iterator();
		it2 = c1.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
			w2 = it2.next().intValue();
			
			peso += this.pes.getPos(w1, w2);
		}
		
		it = c2.iterator();
		it2 = c2.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
			w2 = it2.next().intValue();
			
			peso += this.pes.getPos(w1, w2);
			}
		
		return peso;
	}

	private void modificarCircuitos(MejorParcial mp) {
		if(mp.getCircuitoSacar()==1){
			this.circuito1.remove(mp.getIndex());
		}else{
			this.circuito2.remove(mp.getIndex());		
		}
		
		if(mp.getCircuitoPoner()==1){
			this.circuito1.add(mp.getPos2(), new Integer(mp.getI()));
		}else{
			this.circuito2.add(mp.getPos2(), new Integer(mp.getI()));
		}	
	}

	private int calcularCostoDeAgregarIEntreW1yW2(int i, int v1, int v2) {
		int peso = 0;
		int w1, w2;
		
		Iterator<Integer> it, it2;
		
		it = this.circuito1.iterator();
		it2 = this.circuito1.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
			w2 = it2.next().intValue();
			if(w1==v1 && w2==v2){
				peso += this.pesos[w1][i] + this.pesos[i][w2];
			}
			else{
				if(w1==v2 && w2==v1){
					peso += this.pesos[w1][i] + this.pesos[i][w2];
				}
				else{
					peso += this.pesos[w1][w2];
				}
			}
			
		}
		
		it = this.circuito2.iterator();
		it2 = this.circuito2.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
			w2 = it2.next().intValue();
			if(w1==v1 && w2==v2){
				peso += this.pesos[w1][i] + this.pesos[i][w2];
			}
			else{
				if(w1==v2 && w2==v1){
					peso += this.pesos[w1][i] + this.pesos[i][w2];
				}
				else{
					peso += this.pesos[w1][w2];
				}
			}
		}
		return peso;
	}
	
	public int getSolucion(){
		return this.res;
	}
	
	public String getResIter(){
		return res_iter +" " +res_sol;
	}

	public LinkedList<String> getRes_graf() {
		return res_graf;
	}

	public int getRes_iter() {
		return res_iter;
	}

	public int getRes_sol() {
		return res_sol;
	}
	
	public static void main(String[] args) {

	}

}
